1. Technical Field
The present invention relates generally to the display and printing of digital images and, more particularly, to methods of coalescing a mosaic of separate digital image tiles, each tile presented in the form of a discrete bitmap, into a single bitmap for artifact-free image enhancement, and to methods of testing tiles to determine when coalescence is contraindicated.
2. Description of Related Art
Computer generation and processing of digital images is a vital component of present information technology. Computers have displayed information to the outside world in progressively more complex formats from alphanumeric, monochrome charts and graphs, and presently in full color images comparable in quality with the best photographs. Digital creation, manipulation and display of images is an expanding field of computer technology showing no signs of deceleration. Very few application programs are made commercially available that do not have capabilities for creating, manipulating or using high quality images for ease of program use, simplicity of communication with the user, or for entertainment, games or advertising. Thus, the engineer concerned with computer display and printing technologies must consider full color (typically 24 bit) and high resolution (typically 600 dpi) images.
The present invention relates to the interface between two digital imaging technologies; digital image enhancement and the display, printing and/or assembly of composite images from subimages referred to as xe2x80x9ctiling.xe2x80x9d xe2x80x9cTilingxe2x80x9d is the process by which a single image is constructed from several (or very many) separate components or xe2x80x9ctilesxe2x80x9d that are assembled into the proper spatial relationship to construct the full image. Thus, the complete image is constructed as a xe2x80x9cmosaicxe2x80x9d of individual tiles. Some application programs may construct separate tiles and display (or print) each tile in the proper spatial relationship to form the complete image.
Many areas of technology are presented with the problem of assembling a single coherent image from numerous component subimages. One typical example relates to satellite photography in which an orbiting satellite acquires numerous sequential images of the scene below. These separate images (xe2x80x9ctilesxe2x80x9d) are to be assembled into a single composite image (xe2x80x9cmosaicxe2x80x9d). The process of assembling tiles into a mosaic is to be done in such a manner that it is not apparent to the viewer or user of the final mosaic image that it was assembled from tiles. The work of Burt et. al. describes ways of assembling mosaic images from tiles in U.S. Pat. Nos. 5,488,674 and 5,649,032. Schemes for matching common features and aligning adjacent tiles are described.
Other areas of technology also involve the assembly of mosaic images from tiles. For example, Adelson (U.S. Pat. No. 4,661,986) describes the assembly of a three dimensional image from a collection of two dimensional images of the same scene. Assembling a composite image from a series of electron micrographs is described in the work of Vogt and Trenkle (U.S. Pat. No. 5,796,861). These examples are intended to be illustrative only and not exhaust all areas of technology in which mosaic images are assembled from tiles.
However, these examples of assembling an image from tiles share a common feature in so far as it is known from the start that the images relate to the same scene. Aerial, satellite panoramic video or still photography typically depict variations of a single scene. That is, the user knows or presumes that the image tiles ought to be assembled into a single, composite mosaic image in which the separate tiles form a non-disjoint image. In addition, it is often the case that automated schemes of mosaic construction utilize the fact that consecutive images overlap, simplifying the search for common features for matching. Distinct images typically call for separate and distinct uses of the methods described by these prior works.
In the display or printing of computer generated images, the situation is more complex. FIG. 1 depicts a typical page that a computer user would wish to print (often in color, unlike FIG. 1). Application programs may create numerous tiles that need to be joined to form the separate images of giraffe (FIG. 1B), hot rod (FIG. 1C), etc. However, separate tiles forming components of distinct images (hot rod 1C, and hockey player 1D, for example) should not be joined but remain distinct images as the user has placed them on the page as depicted in FIG. 1. Therefore, any automated scheme for assembling tiles into a mosaic image must have the capability of joining tiles for a single image, and not joining tiles when separate images occur on a single page. This should be contrasted with previous tiling methods such as those noted above in which typically only a single image is under consideration, analogous to the image of FIG. 2.
Digital data for creating pages or screen displays must include in some form the particular location at which each picture element, or xe2x80x9cpixel,xe2x80x9d is to be displayed and the color to be displayed at that particular pixel. However, modem display and printing technology is more complex than a simple rendering of pixel-by-pixel information onto the appropriate page or screen location. Color mapping, image enhancements and many other image processing procedures may be employed to render the colors on the printed page so that they appear to match, enhance contrast and/or resolution and provide myriad other image enhancements. It is imperative that image enhancements be carried out without introducing artifacts into the image. That is, while enhancing one image feature (such as contrast) artifacts (such as lines or bands) should not be created so as to detract from the overall image quality. Additionally, such image processing procedures must be rapidly performed so as not to reduce substantially the printing speed of each page or introduce annoying delays into screen displays. The interaction of tiling technologies with image enhancement technologies is the general field of the present invention.
It is convenient to consider two classes of image alteration or enhancement. A first class relates to a xe2x80x9clocalxe2x80x9d transformation of the information in the image. That is, an image is altered pixel by pixel such that the alteration (transformation) applied to any pixel does not depend on the characteristics, alteration or transformation of any other pixel. Color mapping is a typical example of such a local image transformation in which the numerical color value of the screen display is altered to produce a printed pixel having a perceived color as close as possible to the color perceived by the viewer on the screen display. Users desire color on a printed page to be the same as that on the screen. This requires an analysis of the different color perception qualities of the images created by different devices and appropriate corrections. Such color correction is a typical example of local transformation of one image pixel into another image pixel in which the characteristics of other pixels are not considered in creating or applying the transformation. Many other local transformations may be employed as well.
In contrast to local image transformations are a variety of image enhancing procedures that depend on an analysis of several (or many) pixels for determining the characteristics and parameters of the subsequent image transformation. Such transformation depending on more than a single local pixel we denote as xe2x80x9cnon-localxe2x80x9d or xe2x80x9cglobal.xe2x80x9d Spatially sensitive filters are another name often used to denote image enhancements making use of more than the local pixel to be transformed in determining the operation to be applied. Spatially sensitive filtering applies a transformation to each pixel of the image in which the transformation applied to any particular pixel is determined by the properties of several (or many) pixels in addition to the pixel being transformed. Spatially sensitive filtering may use the properties of the entire image or bitmap or tile in determining the transformation to be applied to each particular pixel. Other examples of spatially sensitive filtering procedures include techniques are known in the art as well as vendor-specific products such as xe2x80x9cresolution synthesis with downsamplingxe2x80x9d and xe2x80x9cautomatic contrast enhancement,xe2x80x9d both developed by Hewlett Packard. Another procedure offered by Hewlett Packard is xe2x80x9cresolution synthesis without downsampling,xe2x80x9d a local image transformation.
However useful global image transformations may be in enhancing the image quality for the viewer, special challenges arise when used in combination with tiling. Global image transformations may use all or a substantial portion of the tile to determine the transformation applied to each pixel in the tile. Thus, different tiles will have different global properties and generate different transformations to be applied to each pixel in that particular tile. When the separate tiles are reassembled into the full image, imperfect matching at the tile-tile boundaries may be apparent. One example of such transformation-induced artifacts is depicted in FIG. 2.
FIG. 2 was delivered by the application as tiles and assembled on the page as a sequence of horizontal stripes (the tiles) stored in the computer as a sequence of bitmaps. A global image enhancement procedure was applied to the image for the purpose of enhancing contrast. Such an image enhancement is a global transformation examining the properties of the entire tile before determining the transformation to be applied to each pixel within the tile. We note as 1 in FIG. 2 an artifact of the type that may result from such a tile-by-tile global image transformation. Tile 1 in FIG. 2 contains a larger proportion of dark region than the tiles immediately adjacent above and below. Thus, automatic application of the contrast enhancement procedure to each tile in sequence produces an overly light stripe, 1, detracting from the image quality. Thus, the benefits of automatic contrast enhancement in this case are squandered and, indeed, result in poorer image quality than had the transformation not been applied at all. The benefits of such automatic contrast enhancements are most apparent in color prints, unlike FIG. 2. However, FIG. 2 adequately depicts the image artifacts that may be introduced by automatic application of a global image transformation.
The present invention has a dual approach to image processing. Firstly, the present invention causes the tiles of a single image (FIG. 2 or each individual image 1A-1J of FIG. 1) to be assembled for global processing in such a manner that artifacts will not be created in subsequent global image enhancement procedures. That is, artifact 1 in FIG. 2 would be absent had FIG. 2 be processed according to the procedures of the present invention.
Additionally, the present invention recognizes distinct images on a single page (FIG. 1) as distinct and applies global image enhancements only within each distinct image (or not applied at all in particularly disadvantageous cases). Thus, pursuant to the present invention, artifacts arising from global image enhancements are suppressed by pre-assembly of tiles when possible. Another component of the present invention is the recognition of images in which application of global image enhancements carries significant danger of introducing artifacts, but which are not readily amenable to artifact-avoiding strategies. For such cases, the preferred route is to apply no global image enhancements at all. Recognition of such cases and avoidance of artifacts even at the cost of avoiding all image enhancements is a component of the present invention.
The present invention relates to methods of coalescing device independent bitmaps (xe2x80x9cDIBsxe2x80x9d) into images for rendering onto a printed page such that artifacts induced by global techniques for image enhancement are avoided. The present invention has a dual approach to image processing. Firstly, the present invention causes the tiles of a single image to be assembled for global processing in such a manner that artifacts will not be created in subsequent global image enhancement procedures. Additionally, the present invention recognizes distinct images on a single page as distinct and applies global image enhancements only within each distinct image (or not applied at all in particularly disadvantageous cases). Thus, pursuant to the present invention, artifacts arising from global image enhancements are suppressed by pre-assembly of tiles when possible. Another component of the present invention is the recognition of images in which application of global image enhancements carries significant danger of introducing artifacts, but which are not readily amenable to artifact-avoiding strategies. For such cases, the preferred route is to apply no global image enhancements at all. Recognition of such cases and avoidance of artifacts even at the cost of avoiding all image enhancements is a component of the present invention.